package com.xzz.dfs;

/**
 * @author: hhz
 * @create: 2022-01-24 13:48
 * 200. 岛屿数量
 **/
public class NumIslands {
    public static void main(String[] args) {
        System.out.println(numIslands(new char[][]{{'1','1','1','1','0'},{'1','1','0','1','0'},{'1','1','0','0','0'},{'0','0','0','0','0'}}));
        System.out.println(numIslands(new char[][]{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}}));
    }
    public static int numIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(grid[i][j]=='1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    //dfs 深度优先算法，将岛屿淹没
    public static void dfs(char[][] grid,int i,int j) {
        if(i>=grid.length || i<0 || j>=grid[0].length || j<0){
            return ;
        }
        if(grid[i][j]=='0'){
            return ;
        }
        grid[i][j]='0';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
}
